k-meansクラスタリング（k-means clustering）

Overview

k-meansクラスタリングは、最も単純で最も広く用いられているクラスタリングアルゴリズムです。k-meansは、データのある領域を代表するようなクラスタ重心を見つけようとします。

Theory

k-meansの挙動

https://gyazo.com/707e03a5fcd9040427999d9819785a63

上図は、データポイントを丸、クラスタセンタを三角形で示しています。次のような手順で行われています。

任意の個数（上では3つ）のデータポイントをクラスタセンタとして乱数で選ぶ（初期化）

これらを繰り返し行う

個々のデータポイントが最も近いクラスタセンタに割り当てられる

割り当てられた点の平均にクラスタセンタを更新する

クラスタセンタが動かなくなるまで繰り返す

新しいデータポイントが与えられた場合は、クラスタセンタのうち最も近いものに割り当てる

Coding

合成データセットにk-meansクラスタリングを適用する

code: Python

from sklearn.datasets import make_blobs

from sklearn.cluster import KMeans

# 合成2次元データを作る

X, y = make_blobs(random_state=1)

# クラスタリングモデルを作る（クラスタ数は3つ）

kmeans = KMeans(n_clusters=3)

# 個々の訓練データポイントに対して、クラスタラベルが割り当てられる

kmeans.fit(X)

# 割り当てられたラベルはkmeans.labels_属性で確認できる

print('Cluster memberships:\n{}'.format(kmeans.labels_))

--------------------------------------------------------------------------

Cluster memberships:

[1 2 2 2 0 0 0 2 1 1 2 2 0 1 0 0 0 1 2 2 0 2 0 1 2 0 0 1 1 0 1 1 0 1 2 0 2

2 2 0 0 2 1 2 2 0 1 1 1 1 2 0 0 0 1 0 2 2 1 1 2 0 0 2 2 0 1 0 1 2 2 2 0 1

1 2 0 0 1 2 1 2 2 0 1 1 1 1 2 1 0 1 1 2 2 0 0 1 0 1]

--------------------------------------------------------------------------

3つのクラスタを作るように指定したのでクラスタラベルは0から2となっています。クラスタセンタはcluster_centers_属性に格納されているので、これを三角形でプロットします。

code: Python

import mglearn

https://gyazo.com/6f7625cd402b0eb4397bd2022936c5c6

Advanced

k-meansクラスタリングがうまくいかない場合

k-meansは、クラスタセンタへの距離しか考慮しないので、複雑な形にはうまく機能しません。下の例では、cluster2に分類されそうなものまで、cluster0、cluster1に分類されてしまっています。

code: Python

y_pred = KMeans(n_clusters=3, random_state=0).fit_predict(X_varied)

plt.xlabel("Feature 0")

plt.ylabel("Feature 1")

https://gyazo.com/2c870dc2b78fc5fab262483cb342409b

また、下図を例に見てみます。視覚的には明らかに3つに分かれていますが、距離しか考慮しないためにクラスタリングに失敗しています。

code: Python

X, y = make_blobs(random_state=170, n_samples=600)

rng = np.random.RandomState(74)

transformation = rng.normal(size=(2, 2))

X = np.dot(X, transformation)

kmeans = KMeans(n_clusters=3)

kmeans.fit(X)

y_pred = kmeans.predict(X)

plt.xlabel("Feature 0")

plt.ylabel("Feature 1")

https://gyazo.com/8fdbfb1180e0ed8e58f6474ac849216b

複雑な形のデータセットでも見てみます。

code: Python

from sklearn.datasets import make_moons

X, y = make_moons(n_samples=200, noise=0.05, random_state=0)

kmeans = KMeans(n_clusters=2)

kmeans.fit(X)

y_pred = kmeans.predict(X)

plt.xlabel("Feature 0")

plt.ylabel("Feature 1")

https://gyazo.com/f939d056dce5285b271e32df7d29aa3c

成分分解としてのk-means（ベクトル量子化）

k-meansは、PCAやNMFと同じように、成分分解手法としても用いることができます。 PCAが最も分散が大きい方向群を見出そうとし、NMFは足しこんでいくことのできる成分を見つけようとするに対し、k-meansはクラスタセンタとして与えられる単一の成分で表現します。k-meansを単一成分で個々のデータポイントを表現する成分分解手法としてみる考え方を、ベクトル量子化といいます。

two_moonsデータセットを例に見てみます。PCAやNMFではこのデータセットにできることはほとんどありません。2次元のデータセットなので、次元削減してしまうと完全にデータが壊れてしまいます。しかし、k-meansでは、多数のクラスタセンタを用いてより強力な表現を得ることができます。

code: Python

X, y = make_moons(n_samples=200, noise=0.05, random_state=0)

kmeans = KMeans(n_clusters=10, random_state=0)

kmeans.fit(X)

y_pred = kmeans.predict(X)

plt.xlabel("Feature 0")

plt.ylabel("Feature 1")

print("Cluster memberships:\n{}".format(y_pred))

--------------------------------------------------------------------------

Cluster memberships:

[9 2 5 4 2 7 9 6 9 6 1 0 2 6 1 9 3 0 3 1 7 6 8 6 8 5 2 7 5 8 9 8 6 5 3 7 0

9 4 5 0 1 3 5 2 8 9 1 5 6 1 0 7 4 6 3 3 6 3 8 0 4 2 9 6 4 8 2 8 4 0 4 0 5

6 4 5 9 3 0 7 8 0 7 5 8 9 8 0 7 3 9 7 1 7 2 2 0 4 5 6 7 8 9 4 5 4 1 2 3 1

8 8 4 9 2 3 7 0 9 9 1 5 8 5 1 9 5 6 7 9 1 4 0 6 2 6 4 7 9 5 5 3 8 1 9 5 6

3 5 0 2 9 3 0 8 6 0 3 3 5 6 3 2 0 2 3 0 2 6 3 4 4 1 5 6 7 1 1 3 2 4 7 2 7

3 8 6 4 1 4 3 9 9 5 1 7 5 8 2]

--------------------------------------------------------------------------

https://gyazo.com/8edaf91e7b7a9bca577f6e43391d45c2

上図では、10のクラスタセンタを用いています。したがって、個々のデータポイントには0から9の番号が割り当てられています。これは、10個の新しい特徴量ができたことになります。そうすると、この2つの半月型を線形モデルで分離できます。さらに、個々のクラスタセンタからの距離を特徴量として用いれば、さらに強力な表現となります。

code: Python

distance_features = kmeans.transform(X)

print('Distance feature shape: {}'.format(distance_features.shape))

print('Distance features:\n{}'.format(distance_features))

--------------------------------------------------------------------------

Distance feature shape: (200, 10)

Distance features:

...

--------------------------------------------------------------------------